{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T13:46:34.338949Z",
     "start_time": "2020-02-11T13:46:34.330047Z"
    }
   },
   "outputs": [],
   "source": [
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int): #-> List[List[int]]:\n",
    "        '''\n",
    "        A, lo = [], n*n+1\n",
    "        while lo > 1:\n",
    "            lo, hi = lo - len(A), lo\n",
    "            A = [range(lo, hi)] + [*zip(*A[::-1])]\n",
    "        return A\n",
    "        '''\n",
    "        out = []\n",
    "        for i in range(n):\n",
    "            out.append([0]*n)\n",
    "        direct = 0\n",
    "        step_c = [1,0,-1,0]\n",
    "        step_r = [0,1,0,-1]\n",
    "        steps = n\n",
    "        cols = n\n",
    "        rows = n\n",
    "        r = 0\n",
    "        c = -1\n",
    "        i = 1\n",
    "        while(cols > 0 and rows > 0):\n",
    "            for j in range(steps):\n",
    "                r += step_r[direct]\n",
    "                c += step_c[direct]\n",
    "                out[r][c] = i\n",
    "                i += 1\n",
    "            if(direct % 2 == 0):\n",
    "                rows -= 1\n",
    "                steps = rows\n",
    "            else :\n",
    "                cols -= 1\n",
    "                steps = cols\n",
    "            direct = (direct +1) % 4\n",
    "        return out\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T13:46:40.000905Z",
     "start_time": "2020-02-11T13:46:39.996247Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2, 3], [8, 9, 4], [7, 6, 5]]\n",
      "[[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]\n"
     ]
    }
   ],
   "source": [
    "a = Solution()\n",
    "print(a.generateMatrix(3))\n",
    "print(a.generateMatrix(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 其他方法\n",
    "-----------------\n",
    "\n",
    "<div class=\"post-area__3YJL\"><div class=\"root__3bcS\"><div class=\"user-info__2b-x\"><a href=\"/stefanpochmann\" target=\"_blank\"><img></a><span class=\"name__2jm2\"><a href=\"/stefanpochmann\" target=\"_blank\" class=\"link__Lpjq\">StefanPochmann</a></span><span class=\"reputation___jPr\"><svg viewBox=\"0 0 24 24\" width=\"1em\" height=\"1em\" class=\"icon__3Su4\"><path fill-rule=\"evenodd\" d=\"M12 17.27L18.18 21l-1.64-7.03L22 9.24l-7.19-.61L12 2 9.19 8.63 2 9.24l5.46 4.73L5.82 21z\"></path></svg>43067</span><div style=\"position: absolute; top: 0px; left: 0px; width: 100%;\"><div><div class=\"ant-tooltip lc-tooltip ant-tooltip-placement-top  ant-tooltip-hidden\" style=\"left: 219.8px; top: -37px; transform-origin: 50% 44.8px;\"><div class=\"ant-tooltip-content\"><div class=\"ant-tooltip-arrow\"></div><div class=\"ant-tooltip-inner\" role=\"tooltip\">Reputation</div></div></div></div></div></div><div class=\"post-info__1K06\"><p>Last Edit: October 18, 2018 11:58 PM</p><p class=\"view-count__dBuq\">24.7K VIEWS</p></div></div><div class=\"content-area__2vnF\"><div class=\"discuss-markdown-container\"><p><strong>Solution 1: <em>Build it inside-out</em></strong> - 44 ms, 5 lines</p><p>\n",
    "</p><p>Start with the empty matrix, add the numbers in reverse order until we added the number 1. Always rotate the matrix <wdautohl-customtag style=\"font-weight:bold;color:red;font-size:inherit;display:inline;\" id=\"wdautohl_id_3\" class=\"wdautohl_Y2xvY2t3aXNl\">clockwise</wdautohl-customtag> and add a top row:</p><p>\n",
    "</p><pre><code>    ||<span class=\"hljs-string\">  =&gt;  </span>|<span class=\"hljs-string\">9</span>|<span class=\"hljs-string\">  =&gt;  </span>|<span class=\"hljs-string\">8</span>|<span class=\"hljs-string\">      </span>|<span class=\"hljs-string\">6 7</span>|<span class=\"hljs-string\">      </span>|<span class=\"hljs-string\">4 5</span>|<span class=\"hljs-string\">      </span>|<span class=\"hljs-string\">1 2 3</span>|\n",
    "                     |<span class=\"hljs-string\">9</span>|<span class=\"hljs-string\">  =&gt;  </span>|<span class=\"hljs-string\">9 8</span>|<span class=\"hljs-string\">  =&gt;  </span>|<span class=\"hljs-string\">9 6</span>|<span class=\"hljs-string\">  =&gt;  </span>|<span class=\"hljs-string\">8 9 4</span>|\n",
    "                                         |<span class=\"hljs-string\">8 7</span>|<span class=\"hljs-string\">      </span>|<span class=\"hljs-string\">7 6 5</span>|\n",
    "</code></pre>\n",
    "<p></p><p>The code:</p><p>\n",
    "</p><pre><code>def generateMatrix(self, n):\n",
    "    A, <span class=\"hljs-keyword\">lo</span> = [], n*n+<span class=\"hljs-number\">1</span>\n",
    "    <span class=\"hljs-keyword\">while</span> <span class=\"hljs-keyword\">lo</span> &gt; <span class=\"hljs-number\">1</span>:\n",
    "        <span class=\"hljs-keyword\">lo</span>, <span class=\"hljs-keyword\">hi</span> = <span class=\"hljs-keyword\">lo</span> - <span class=\"hljs-built_in\">len</span>(A), <span class=\"hljs-keyword\">lo</span>\n",
    "        A = [<span class=\"hljs-built_in\">range</span>(<span class=\"hljs-keyword\">lo</span>, <span class=\"hljs-keyword\">hi</span>)] + zip(*A[::-<span class=\"hljs-number\">1</span>])\n",
    "    <span class=\"hljs-keyword\">return</span> A\n",
    "</code></pre>\n",
    "<p></p><p>While this isn't O(n^2), it's actually quite fast, presumably due to me not doing much in Python but relying on <code>zip</code> and <code>range</code> and <code>+</code> being fast. I got it accepted in 44 ms, matching the fastest time for recent Python submissions (according to the submission detail page).</p><p>\n",
    "</p><hr>\n",
    "<p></p><p><strong>Solution 2: <em>Ugly inside-out</em></strong> - 48 ms, 4 lines</p><p>\n",
    "</p><p>Same as solution 1, but without <wdautohl-customtag style=\"font-weight:bold;color:red;font-size:inherit;display:inline;\" id=\"wdautohl_id_4\" class=\"wdautohl_aGVscGVy\">helper</wdautohl-customtag> variables. Saves a line, but makes it ugly. Also, because I access A[0][0], I had to handle the n=0 case differently.</p><p>\n",
    "</p><pre><code>def generateMatrix(self, n):\n",
    "    A = [[n*n]]\n",
    "    <span class=\"hljs-keyword\">while</span> A[<span class=\"hljs-number\">0</span>][<span class=\"hljs-number\">0</span>] &gt; <span class=\"hljs-number\">1</span>:\n",
    "        A = [range(A[<span class=\"hljs-number\">0</span>][<span class=\"hljs-number\">0</span>] - len(A), A[<span class=\"hljs-number\">0</span>][<span class=\"hljs-number\">0</span>])] + zip(*A[::<span class=\"hljs-number\">-1</span>])\n",
    "    <span class=\"hljs-keyword\">return</span> A * (n&gt;<span class=\"hljs-number\">0</span>)\n",
    "</code></pre>\n",
    "<hr>\n",
    "<p></p><p><strong>Solution 3: <em>Walk the spiral</em></strong> - 52 ms, 9 lines</p><p>\n",
    "</p><p><wdautohl-customtag style=\"font-weight:bold;color:red;font-size:inherit;display:inline;\" id=\"wdautohl_id_5\" class=\"wdautohl_aW5pdGlhbGl6ZQ__\">Initialize</wdautohl-customtag> the matrix with zeros, then walk the spiral path and write the numbers 1 to n*n. Make a right turn when the cell ahead is already non-zero.</p><p>\n",
    "</p><pre><code>def generateMatrix(self, n):\n",
    "    A = [[<span class=\"hljs-number\">0</span>] * n <span class=\"hljs-keyword\">for</span> _ in <span class=\"hljs-built_in\">range</span>(n)]\n",
    "    i, <span class=\"hljs-keyword\">j</span>, <span class=\"hljs-keyword\">di</span>, <span class=\"hljs-keyword\">dj</span> = <span class=\"hljs-number\">0</span>, <span class=\"hljs-number\">0</span>, <span class=\"hljs-number\">0</span>, <span class=\"hljs-number\">1</span>\n",
    "    <span class=\"hljs-keyword\">for</span> <span class=\"hljs-keyword\">k</span> in xrange(n*n):\n",
    "        A[i][<span class=\"hljs-keyword\">j</span>] = <span class=\"hljs-keyword\">k</span> + <span class=\"hljs-number\">1</span>\n",
    "        <span class=\"hljs-keyword\">if</span> A[(i+<span class=\"hljs-keyword\">di</span>)%n][(<span class=\"hljs-keyword\">j</span>+<span class=\"hljs-keyword\">dj</span>)%n]:\n",
    "            <span class=\"hljs-keyword\">di</span>, <span class=\"hljs-keyword\">dj</span> = <span class=\"hljs-keyword\">dj</span>, -<span class=\"hljs-keyword\">di</span>\n",
    "        i += <span class=\"hljs-keyword\">di</span>\n",
    "        <span class=\"hljs-keyword\">j</span> += <span class=\"hljs-keyword\">dj</span>\n",
    "    <span class=\"hljs-keyword\">return</span> A</code></pre><p></p></div></div><div class=\"tag-list-container__2cDj\"><div class=\"css-9sdfuf\"><span class=\"css-vh6pmz\">python</span><span class=\"css-vh6pmz\">short</span></div></div></div>"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Attachments",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
